# 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
#
# 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
# 要求：时间复杂度 O(nlogn)O(nlogn)，空间复杂度 O(1)O(1)
# 数据范围：0\le n \le 10000≤n≤1000， 1 \le K \le n1≤K≤n，数组中每个元素满足 0 \le val \le 100000000≤val≤10000000
# 示例1
# 输入：
# [1,3,5,2,2],5,3
# 复制
# 返回值：
# 2
# 复制
# 示例2
# 输入：
# [10,10,9,9,8,7,5,6,4,3,4,2],12,3
# 复制
# 返回值：
# 9
# 复制
# 说明：
# 去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9

from queue import PriorityQueue
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param a int整型一维数组
# @param n int整型
# @param K int整型
# @return int整型
#
from typing import List
from queue import PriorityQueue


class Solution:
    def findKth(self, a: List[int], n: int, K: int) -> int:
        top_k = PriorityQueue()

        i = 0
        for each in a:
            top_k.put(each)
            i += 1
            if i >= K + 1:
                top_k.get()

        return top_k.get()


solution = Solution()
assert solution.findKth([1, 3, 5, 2, 2], 5, 3) == 2
assert solution.findKth([10, 10, 9, 9, 8, 7, 5, 6, 4, 3, 4, 2], 12, 3) == 9
